#include <vector>
#include <iostream>

using namespace std;

class Solution {
    /*
private:
    vector<int>* prices;
    int buy(int day, int k, int buy_price, int profit) {
        if (day == prices->size() || k == 0 || buy_price != INT32_MIN) {
            return profit;
        }
        return max(hold(day + 1, k, prices->at(day), profit), sell(day + 1, k, prices->at(day), profit));
    }
    int hold(int day, int k, int buy_price, int profit) {
        if (day == prices->size() || k == 0) {
            return profit;
        }
        return max(max(hold(day + 1, k, buy_price, profit), buy(day + 1, k, buy_price, profit)), sell(day + 1, k, buy_price, profit));
    }
    int sell(int day, int k, int buy_price, int profit) {
        if (day == prices->size() || k == 0 || buy_price == INT32_MIN) {
            return profit;
        }
        profit += prices->at(day) - buy_price;
        return max(hold(day + 1, k - 1, INT32_MIN, profit), buy(day + 1, k - 1, INT32_MIN, profit));
    }
public:
    int maxProfit(int k, vector<int>& prices) {
        this->prices = &prices;
        return max(hold(0, k, INT32_MIN, 0), buy(0, k, INT32_MIN, 0));
    }
     */
public:
    int maxProfit(int k, vector<int>& prices) {
        if (k * 2 > prices.size()) {
            int profit = 0;
            for (int i = 0, length = prices.size() - 1; i < length; i++) {
                if (prices[i + 1] > prices[i]) {
                    profit += prices[i + 1] - prices[i];
                }
            }
            return profit;
        }
        vector<vector<int>> profit(k + 1, vector<int>({0, INT32_MIN}));
        for (int i = 0; i < prices.size(); i++) {
            for (int j = 1; j <= k; j++) {
                profit[j][0] = max(profit[j][0], profit[j][1] + prices[i]);
                profit[j][1] = max(profit[j][1], profit[j - 1][0] - prices[i]);
            }
        }
        return profit[k][0];
    }
};

int main() {
    vector<int> input = {3, 2, 6, 5, 0, 3};
    Solution solution;
    int output = solution.maxProfit(2, input);
    cout << output << endl;
    return 0;
}
